function ArrayList() {
  this.array = []
  ArrayList.prototype.insert = (item) => {
    this.array.push(item)
  }
  ArrayList.prototype.toString = () => {
    return this.array.join('-')
  }

  ArrayList.prototype.swap = (m, n) => {
    var temp = this.array[m]
    this.array[m] = this.array[n]
    this.array[n] = temp
  }

  // 冒泡 O(n2)
  ArrayList.prototype.bubblesort = () => {
    var length = this.array.length
    for (var j = length - 1; j >= 0; j--) {
      for (var i = 0; i < j; i++) {
        if (this.array[i] > this.array[i + 1]) {
          this.swap(i, i + 1)
        }
      }
    }
  }

  // 选择排序 比较O(n2) 交换O(n)
  ArrayList.prototype.selectionSort = () => {
    var length = this.array.length
    for (var j = 0; j < length - 1; j++) {
      var min = j
      for (var i = min + 1; i < length; i++) {
        if (this.array[min] > this.array[i]) {
          min = i
        }
      }
      this.swap(min, j)
    }
  }

  ArrayList.prototype.insertionSort = () => {
    var length = this.array.length
    for (var i = 1; i < length; i++) {
      var temp = this.array[i]
      var j = i
      while (this.array[j - 1] > temp && j > 0) {
        this.array[j] = this.array[j - 1]
        j--
      }
      this.array[j] = temp
    }
  }

  ArrayList.prototype.shellSort = () => {
    var length = this.array.length
    var gap = Math.floor(length / 2)
    while (gap >= 1) {
      for (var i = gap; i < length; i++) {
        var temp = this.array[i]
        var j = i
        while (this.array[i - gap] > temp) {
          this.array[j] = this.array[i - gap]
          j -= gap
        }
      }
      this.array[j] = temp
    }
    gap = Math.floor(gap / 2)
  }

  ArrayList.prototype.median = (left, right) => {
    var center = Math.floor((left + right) / 2)
    if (this.array[left] > this.array[center]) {
      this.swap(left, center)
    }
    if (this.array[center] > this.array[right]) {
      this.swap(center, right)
    }
    if (this.array[left] > this.array[right]) {
      this.swap(left, right)
    }

    this.swap(center, right - 1)
    return this.array[right - 1]
  }

  ArrayList.prototype.quickSort = () => {
    this.quick(0, this.array.length - 1)
  }
  ArrayList.prototype.quick = () => {
    if (left >= right) return

    var pivot = this.median(left, right)

    var i = left
    var j = right - 1

    while (true) {
      while (this.array[++i] < pivot) {}
      while (this.array[--j] > pivot) {}
      if (i < j) {
        this.swap(i, j)
      } else {
        break
      }
    }
    this.swap(i, right - 1)
    this.quick(left, i - 1)
    this.quick(i + 1, right)
  }
}

var list = new ArrayList()

list.insert(66)
list.insert(88)
list.insert(12)
list.insert(87)
list.insert(100)
list.insert(5)
list.insert(566)
list.insert(23)